Many data streams (e.g. files) are often stored on a single storage medium, such as a hard disk. The storage medium is divided into sectors, and each data stream is assigned enough sectors to hold all of its data. Each sector can be assigned to only one data stream. A data stream can be viewed as being divided up into a consecutive set of blocks, where each block is the size of a sector. Each block of a data stream is stored in a different sector of the storage medium.
All blocks of a data stream are not necessarily located in successive sectors, but, rather, may be interleaved with blocks of several other data streams in the storage medium. Data streams that have blocks or groups of blocks interleaved with blocks of other data streams are called multiplexed data streams.
A known method for managing the storage and retrieval of multiplexed data streams is by means of a data structure known as a linked allocation table (LAT). A LAT is used to locate a selected part of a data stream in the storage medium. It is a table with s entries, where s is the number of sectors in the storage medium. Thus, a storage medium with twice as many sectors as another would have a LAT twice the size. Examples of LATs include the File Allocation Table (FAT) of Microsoft Corporation's DOS and the Block Allocation Table (BAT) of Microsoft Corporation's OLE Storage Format.
A LAT maps blocks of a data stream to sectors of a storage medium. If the sector containing the nth block of a data stream is known, the LAT can be used to find the sector containing the (n+1)th block. It is organized as a set of linked lists, where each linked list is associated with exactly one data stream. Following the links of a linked list in order gives the sector location of each subsequent block of the data stream. For example, given a sector number a (i.e., a sector identified by the number a) containing the first block of a data stream, entry a of the LAT gives the sector number, call it b, containing the second block of the data stream. Entry b of the LAT then gives the sector number containing the third block of the data stream. The linked list is followed in this manner until the location of the desired block of the data stream is determined.
FIG. 1 illustrates a table representing a conventional LAT for a 18 sector storage medium multiplexing two data streams. The labels above the table number the entries of the LAT. Each entry corresponds with a sector of the storage medium. If a sector belongs to a given data stream, then the LAT entry corresponding to that sector specifies the sector number of the next block in the data stream.
In the table illustrated in FIG. 1, the first block of the first data stream begins at sector zero. The location of the first block of a data stream is stored in a "directory" that usually resides on a reserved set of sectors or as a data stream on the storage medium. When the storage medium is formatted before use, a sufficient number of sectors can be reserved for storing the directory. If a data stream needs to be accessed, the location of the first block is found in the directory.
Referring again to FIG. 1, looking at entry 0, which corresponds to sector 0, in the LAT tells us that the next block of the data stream is located at sector 1. Entry 1 of the LAT indicates that the third block of the data stream is located at sector 2, and entry 2 shows that the fourth block is at sector 3. Finally, entry 3 has the value -1, indicating that sector 3 contains the last block of the data stream.
The first block of the second data stream begins at sector 6 (this information is obtained from the directory discussed above). Following the links in the manner described above shows that the subsequent blocks of the data stream are located at sectors 7, 9, 10, 11, 14, 15, 16, 17 and 4. The second data stream is an example of a data stream that does not have blocks located in contiguous sectors of the storage medium.
Using the above described methods in order to locate a particular block of a data stream requires that the links be followed until the link for the desired block is reached. The LAT itself is stored in sectors of the storage medium, and, in order to follow the links, the LAT has to be read into memory.
For a storage medium with many sectors, the LAT is large, and storing the whole LAT in memory may not be possible. Thus, portions of the LAT are read into memory as they are needed. For a large data stream or for one whose parts are spread across a large portion of the storage medium, many reads may be required just to bring the necessary portions of the LAT into memory. These reads can be time consuming and can take up a large portion of the total time required to access portions of a data stream. Additionally, the reads use up a lot of valuable memory.
Therefore, it is desirable to have a faster and more memory efficient method for determining the location of a sector containing a particular block of a data stream than is currently known.